Ottimizzazione Convessa: Oltre la Convessità di Base: Conservazione tramite Supremo Puntuale

Mentre la convessità di base copre somme e scalatura, la conservazione della convessità tramite il supremo puntuale è un'operazione fondamentale per costruire funzioni convessive non banali e stabilire la dualità. Afferma che anche se abbiamo una famiglia non numerabile di funzioni convessive, il loro "inviluppo superiore" rimane convesso. Questo ponte ci permette di analizzare forme convessive complesse utilizzando semplici componenti lineari.

1. La Definizione Tecnica

Per una famiglia di funzioni $\{f(\cdot, y) \mid y \in \mathcal{A}\}$, il supremo puntuale è definito come:

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y)$$

Il dominio di questa funzione è l'insieme dei punti in cui tutte le funzioni della famiglia sono definite e il supremo è finito:

$$\text{dom } g = \{x \mid (x, y) \in \text{dom } f \text{ per ogni } y \in \mathcal{A}, \sup_{y \in \mathcal{A}} f(x, y) < \infty\}$$

L'Approccio dell'Epi-Grafico

Geometricamente, l'epigrafico della funzione supremo è l'intersezione degli epigrafici individuali:

$$\text{epi } g = \bigcap_{y \in \mathcal{A}} \text{epi } f(\cdot, y)$$

Poiché ogni epigrafico individuale è un insieme convesso (a causa della convessità di $f(x, y)$ rispetto a $x$), e l'intersezione di un numero qualsiasi di insiemi convessi è essa stessa convessa, la convessità di $g(x)$ è garantita.

2. Esempi Significativi

Funzione di Supporto: $S_C(y) = \sup \{ y^T x \mid x \in C \}$. Questa funzione è sempre convessa, indipendentemente dal fatto che l'insieme $C$ sia convesso o no, perché è il supremo di funzioni lineari (affini) di $y$.
Distanza dal Punto Più Lontano: $f(x) = \sup_{y \in C} \|x - y\|$. Anche per un insieme $C$ irregolare, $f(x)$ è convessa rispetto a $x$ perché la norma è una funzione convessa di $x$.
Massimo Autovalore: Per una matrice simmetrica $X$, $f(X) = \lambda_{\max}(X)$ è convessa. Questo deriva dal rapporto di Rayleigh: $\lambda_{\max}(X) = \sup\{y^T X y \mid \|y\|_2 = 1\}$. È il supremo di funzioni lineari di $X$.

Teorema: Rappresentazione tramite Funzioni Affini

Teorema

Quasi ogni funzione convessa può essere espressa come il supremo puntuale di una famiglia di funzioni affini (sottostimatori globali).

Intuizione

In ogni punto $x_0$, una funzione convessa $f$ ha un iperpiano di supporto (una funzione affine $h(x) = f(x_0) + g^T(x-x_0)$). Prendendo il supremo di tutti questi iperpiani di supporto, ricostruiamo esattamente la funzione $f$.

🎯 Principio Fondamentale

Il supremo puntuale preserva la convessità e l'inferiore puntuale preserva la concavità. Questo è il segreto della convessità delle norme, delle funzioni spettrali e dei problemi duali.

$$g(x) = \sup_{y \in \mathcal{A}} f(x, y) \implies g \text{ è convessa se } f(\cdot, y) \text{ è convessa } \forall y$$

DOMANDA 1

Se $f_1(x), f_2(x), \dots, f_n(x)$ sono funzioni convessive, cosa possiamo dire su $g(x) = \max\{f_1(x), \dots, f_n(x)\}$?

$g(x)$ è sempre convessa.

$g(x)$ è convessa solo se tutte le $f_i$ sono lineari.

$g(x)$ è concava.

$g(x)$ è solo quasiconvessa.

DOMANDA 2

La funzione di supporto $S_C(y) = \sup_{x \in C} y^T x$ è convessa in $y$ anche se $C$ è un insieme non convesso. Perché?

Perché $y^T x$ è lineare (e quindi convessa) in $y$ per ogni $x$ fissato.

Perché l'insieme $C$ viene automaticamente trattato come il suo inviluppo convesso.

Perché il prodotto scalare è sempre una funzione positiva.

Le funzioni di supporto sono convesse solo se $C$ è limitato.

DOMANDA 3

Qual è la relazione tra l'epigrafico di $g(x) = \sup f_i(x)$ e gli epigrafici individuali $\text{epi } f_i$?

$\text{epi } g = \bigcap \text{epi } f_i$

$\text{epi } g = \bigcup \text{epi } f_i$

$\text{epi } g = \text{conv}(\bigcup \text{epi } f_i)$

Non c'è una relazione diretta.

DOMANDA 4

La norma spettrale di una matrice $\|X\|_2 = \sigma_{\max}(X)$ è convessa perché...

È il supremo delle funzioni convessive $\|Xv\|_2$ sui vettori unitari $v$.

La somma dei valori singolari è sempre convessa.

Tutte le norme sono funzioni lineari.

Le funzioni matriciali sono sempre convessi sul cono semidefinito positivo.

DOMANDA 5

Se prendiamo l'inferiore puntuale di una famiglia di funzioni concave, qual è il risultato?

Una funzione concava.

Una funzione convessa.

Una funzione lineare.

Dipende dal dominio.

Sfida: Dualità e Funzioni Coniugate

MATH008 Analisi Avanzata

Nell'analisi convessa, la funzione coniugata $f^*$ è definita tramite il supremo puntuale di funzioni affini: $f^*(y) = \sup_x (y^T x - f(x))$. Questa trasformazione è fondamentale per i problemi di ottimizzazione duale.

[Risposta Breve] Condizione di secondo ordine per la convessità. Dimostra che una funzione $f$ due volte differenziabile è convessa se e solo se il suo dominio è convesso e $\nabla^2 f(x) \succeq 0$ per ogni $x \in \mathbf{dom} f.

Soluzione: Restringendo $f$ a una linea arbitraria $g(t) = f(x + tv)$, la convessità di $f$ è equivalente a $g''(t) \geq 0$ per ogni $v$ e ogni $t$ tale che $x+tv \in \text{dom } f$. Poiché $g'(t) = \nabla f(x + tv)^T v$ e $g''(t) = v^T \nabla^2 f(x + tv) v$, la condizione $g''(t) \geq 0$ per ogni $v$ è equivalente alla matrice hessiana che sia semidefinita positiva: $\nabla^2 f(x) \succeq 0$.

[Risposta Breve] Gradiente e Hessiano della funzione coniugata. Supponi che $\bar{y}$ e $\bar{x}$ siano legati da $\bar{y} = \nabla f(\bar{x})$, e che $\nabla^2 f(\bar{x}) \succ 0$. (a) Mostra che $\nabla f^*(\bar{y}) = \bar{x}$. (b) Mostra che $\nabla^2 f^*(\bar{y}) = \nabla^2 f(\bar{x})^{-1}$. (Output richiesto: 250 parole)

Risposta di Riferimento dell'Insegnante: Per affrontare la parte (a), ricordiamo la definizione della funzione coniugata $f^*(y) = \sup_x (y^T x - f(x))$. Per un valore fisso $y = \bar{y}$, se $f$ è differenziabile e convessa, il supremo è raggiunto nel punto dove il gradiente dell'obiettivo $h(x) = \bar{y}^T x - f(x)$ si annulla. Impostando $\nabla_x (\bar{y}^T x - f(x)) = 0$ otteniamo $\bar{y} = \nabla f(x)$. Dato che il problema afferma $\bar{y} = \nabla f(\bar{x})$, segue che $\bar{x}$ è il massimizzatore. Per la proprietà della funzione coniugata nel punto di ottimalità, abbiamo $f^*(\bar{y}) = \bar{y}^T \bar{x} - f(\bar{x})$. Derivando entrambi i lati rispetto a $\bar{y}$ e applicando il teorema dell'involucro (o il fatto che $\bar{x}$ sia l'ottimizzatore), otteniamo $\nabla f^*(\bar{y}) = \bar{x}$. Ciò conferma che il gradiente della funzione coniugata agisce come mappa inversa del gradiente della funzione originale.

Per la parte (b), deriviamo la relazione $\nabla f^*(\nabla f(x)) = x$ rispetto a $x$ usando la regola della catena. Questo dà $\nabla^2 f^*(\nabla f(x)) \cdot \nabla^2 f(x) = I$, dove $I$ è la matrice identità. Sostituendo $\bar{y} = \nabla f(\bar{x})$, otteniamo $\nabla^2 f^*(\bar{y}) \cdot \nabla^2 f(\bar{x}) = I$. Poiché ci viene dato $\nabla^2 f(\bar{x}) \succ 0$, l'Hessiano è invertibile. Pertanto, $\nabla^2 f^*(\bar{y}) = [\nabla^2 f(\bar{x})]^{-1}. Questo risultato elegante mostra che la curvatura locale della funzione coniugata è il reciproco (o la matrice inversa) della curvatura della funzione originale nei punti corrispondenti. Questa relazione è centrale nell'analisi dei metodi di tipo Newton nello spazio duale e nella comprensione dei trasformi di Legendre nella fisica e nell'ottimizzazione.